"""
https://leetcode.cn/problems/best-meeting-point
"""

from collections import deque
from typing import List


class Solution:
    def minTotalDistance(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        distance = [[0] * n for _ in range(m)]

        def bfs(i, j):
            q = deque([(i, j)])
            visited = [[False] * n for _ in range(m)]
            visited[i][j] = True
            step = 1
            while q:
                for _ in range(len(q)):
                    x, y = q.popleft()
                    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                            visited[nx][ny] = True
                            distance[nx][ny] += step
                            q.append((nx, ny))
                step += 1

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    bfs(i, j)
                    print("=========================")
                    print(*distance, sep="\n")

        ans = float("inf")
        for i in range(m):
            for j in range(n):
                ans = min(ans, distance[i][j])
        return ans

    def minTotalDistance2(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        rows = []
        cols = []
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    rows.append(i)
        for j in range(n):
            for i in range(m):
                if grid[i][j]:
                    cols.append(j)
        
        # 最近的距离是中位数的地方
        def min_dist_1D(points):
            mid = points[len(points) // 2]
            return sum(abs(mid - p) for p in points)
        
        return min_dist_1D(rows) + min_dist_1D(cols)


grid = [[1, 0, 0, 0, 1], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0]]
print(Solution().minTotalDistance(grid))
